/*
背包
加了约束 条件
*/
#include<bits/stdc++.h>
using namespace std;
struct dd{
    int a,b,c,d;
}mul[160000];
int f[2][160000];
int main(){
    int t,n,h;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&h);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d%d",&mul[i].a,&mul[i].b,&mul[i].c,&mul[i].d);
        int sum=0,ans=0;
        for(int i=1;i<=n;i++){
            if(sum+min(mul[i].a,mul[i].c)>h)break;
            sum+=mul[i].a;
            memset(f[i&1],0,(h+1)*4);
            for(int j=sum;j<=h;j++){
                f[i&1][j]=f[(i-1)&1][j-mul[i].a]+mul[i].b;
                ans=max(f[i&1][j],ans);
            }
            sum=sum-mul[i].a+mul[i].c;
            for(int j=sum;j<=h;j++){
                f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-mul[i].c]+mul[i].d);
                ans=max(f[i&1][j],ans);
            }
            sum-=mul[i].c;
            sum+=min(mul[i].a,mul[i].c);
        }
        memset(f[0],0,(h+1)*4);
        memset(f[1],0,(h+1)*4);
        printf("%d\n",ans);
    }
}